数据结构
一、 选择题（每小题2分，共20分）
1． 折半查找法的时间复杂度是（ ）。
A、 O(n2) B、O(n) C、O(nlog2n) D、O(log2n)
2． 若一个栈的输入序列是1，2，...，n，输出的第一个元素是n，则第i个输出的元素是（ ）。
A、n-i B、i C、n-i+1 D、n-i-1
3． 如果环形链表结构如图1所示，则表达式p->next->next的值是（ ）。
A、15 B、32 C、78 D、全不是
图1
4． 一个n×n的对称矩阵，如果以行或列为主序放入内存，其容量为（ ）。
A、n*n B、n*n/2 C、(n+1)*n/2 D、(n+1)*(n+1)/2
5． 快速排序在（ ）情况下最不利于发挥其长处。
A、被排序的数据量太大 B、被排序的数据中有大量相同
C、被排序的数据基本有序 D、被排序的数据太分散
6． 具有线性结构的数据结构是（ ）。
A、文件结构 B、树结构 C、图结构 D、广义表
7． 在下列网中，（ ）是边不带权值的图。
A、邮电网 B、AOV网 C、公路网 D、AOE网
8． 线索二叉树中某结点为叶子的条件是（ ）。
A、p->lchild!=NULL||p->rchild!=NULL
B、p->ltag==0||p->rtag==0
C、p->lchild!=NULL&&p->rchild!=NULL
D、p->ltag==1 && p->rtag==1
9．给定整数集合{3,5,6,9,12}，与之对应的哈夫曼（Huffman）树是（ ）。
10．图2是一棵( )。
A、4阶B-树 B、4阶B+树
C、3阶B-树 D、3阶B+树
二、 简答题（每小题5分，共30分）
1、 对n个顶点的无向图G，采用邻接矩阵A表示。试问：
（1） 图G有多少条边？
（2） 如何判断顶点i、j之间是否有边相连？
（3） 如何计算一个顶点的度？
2、 如果一棵二叉树n个顶点，用递归算法执行中序遍历。最坏情况时处理递归的栈至少要多少个单元？为什么？
3、 设n0为哈夫曼树的叶子结点数目，简要推导该树的结点总数。
4、 设有循环队列存储在结构变量q中，用C/C++编写元素x入队的算法。
5、 设有n个关键字，它们具有相同的哈希函数值。若采用线性探测法将它们存放到某个哈希表中，至少需要进行多少次探测？为什么？
6、“有序链表”是指什么值有序？其有序性在存储结构上用什么方式表示？
三、 算法设计（25分）
1、 （6分）编写一个函数，从元素类型为int的有序表A中删除所有元素值在（x, y）之间（x≤y，不包括x，y）所有元素。并分析你的算法效率。
2、 （12分）设计算法，将一棵以二叉链表形式存储的二叉树按顺序方式存储到数组A中。算法由以下几个函数组成：
函数count根据树的形态，返回要求顺序存储的数组长度
函数setAry建立指定长度n的动态数组
函数create把二叉树存放到数组中。其中调用count和setAry函数。
3、 （7分）编写算法，求有向图G中距离顶点v的最短路径长度为len的所有顶点。
操作系统部分
1． 试说明进程在三个基本状态之间转换的典型原因（8分）
2． 试修改下面消费者生产者问题解法中的错误（12分）
Producer:
begin
repeat
…
produce an item in nextp;
wait(mutex);
wait(empty);
buffer(in):=nextp;
signal(mutex);
until false;
end
Consumer:
begin
repeat
wait(mutex);
wait(full);
nextc:=buffer(out);
out:=out+1;
signal(mutex);
consume item in nextc;
until false;
end;
3． 什么是抢占式调度，什么是非抢占式调度？（6分）
4． 试说明页面替换算法中的clock算法的基本思想（10分）
5． 在一个请求分页系统中，采用LRU页面置换算法时，假如一个作业的页面走向为：1，3，2，1，1，3，5，1，3，2，1，5，当分配给该作业的物理块数分别为3和4时，试计算在访问过程中所发生的缺页次数和缺页率。（8分）
6． 试说明SPOOLing系统的原理。（8分）
7． 某文件系统采用多级索引的方式组织文件的数据存放，假定在文件的i_node中设有13个地址项，其中直接索引10项，一次间接索引项1项，二次间接索引项1项，三次间接索引项1项。数据块的大小为4k，磁盘地址用4个字节表示，问：（15分）
1） 这个文件系统允许的最大文件长度是多少？
2） 一个2G大小的文件，在这个文件系统中实际占用多少空间？（不包括i_node占用的空间）
8． 什么是对称加密算法和非对称加密算法？（8分）
